package com.jia.explore.dynamicprogramming.knapsack;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @program: Leetcode
 * @description: 多重背包 https://www.acwing.com/problem/content/5/
 *  物品s 可以分为1 2 4 6 8 ... 2^(log(s) - 1) , s - 2^log(s) + 1
 *      根据01背包，取与不取，可以表示 0...s所有的情况
 *      数据范围
 *      0<N≤1000
 *      0<V≤2000
 *      0<vi,wi,si≤2000
 *      物品的个数可以有N * log(s)个，1000 * log(2000) = 11000
 *      01背包，背包大小为2000， 那么总时间复杂度为220000000 10^7
 * @author: STU756
 * @create: 2020-08-11 12:50
 */
public class Dy_MultipleBackpackII {
    static class Goods{
        int v;
        int w;
        public Goods(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Goods> list = new ArrayList<Goods>();
        int n = scanner.nextInt();//物品个数
        int m = scanner.nextInt();//背包的体积
        int index = 1;
        int N = 2020;
        while(index <= n) {
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            int s = scanner.nextInt();
            for(int k = 1; k <= s; k *= 2) {
                s -= k;
                list.add(new Goods(v * k, w * k));
            }

            if(s > 0) list.add(new Goods(v * s, w * s));
            ++index;
        }
        int[] f = new int[N];
        for(Goods g : list) {
            for(int j = m ;j >= g.v; j--) {
                f[j] = Math.max(f[j], f[j - g.v] + g.w);
            }
        }
        System.out.println(f[m]);
    }

}
